/*

冒泡排序通常是最简单的排序算法之一，但它的效率较低，因为每一轮迭代需要多次比较和交换。为了优化冒泡排序，可以考虑以下几种方法：

提前退出：如果在某一轮迭代中没有发生交换，则表明数组已经排序，可以提前退出。这可以减少不必要的迭代。
记录最后交换的位置：可以使用一个变量记录最后一次发生交换的位置，这样可以减少内层循环的范围。
*/

/*
在这个示例中，优化后的冒泡排序函数 optimized_bubble_sort 采用了上述两种优化策略。它通过提前退出和缩小内层循环范围来提高效率。

last_swap_position 用于记录上次交换的位置，这样可以减少不必要的迭代范围。
swapped 标记是否发生了交换，如果一轮迭代没有发生交换，则表明数组已排序，可以提前退出。


*/


#include <stdio.h>
#include <stdbool.h>

// 优化的冒泡排序函数
void optimized_bubble_sort(int arr[], int size) {
    bool swapped;
    int last_swap_position = size - 1;  // 最后一次交换的位置

    for (int i = 0; i < size - 1; i++) {
        swapped = false;
        int new_last_swap_position = 0;  // 用于记录本轮最后一次交换的位置

        for (int j = 0; j < last_swap_position; j++) {  // 只迭代到最后交换位置
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
                new_last_swap_position = j;  // 更新本轮最后交换的位置
            }
        }

        last_swap_position = new_last_swap_position;  // 更新最后交换的位置

        if (!swapped) {  // 如果没有交换，表示数组已排序，提前退出
            break;
        }
    }
}

int main() {
    // 示例数组
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);

    // 执行优化的冒泡排序
    optimized_bubble_sort(arr, size);

    // 输出排序结果
    printf("排序后的数组: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}
